#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# ======================================================
# @File:      : test438
# @Author     : forward_huan
# @Date       : 2024/11/16 21:41
# @Desc       :
# ======================================================
from typing import List


class Solution:
    @staticmethod
    def add_data(data, ch):
        if ch in data:
            data[ch] += 1
        else:
            data[ch] = 1

    @staticmethod
    def pop_data(data, ch):
        data[ch] -= 1
        if data[ch] == 0:
            data.pop(ch)

    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []
        p_len, p_dict, s_dict, result = len(p), {}, {}, []
        for ch in p:
            self.add_data(p_dict, ch)

        for i, ch in enumerate(s):
            self.add_data(s_dict, ch)
            if i < p_len - 1:
                continue
            if s_dict == p_dict:
                result.append(i - p_len + 1)
            self.pop_data(s_dict, s[i - p_len + 1])
        return result


print(Solution().findAnagrams(s="cbaebabacd", p="abc"))
print(Solution().findAnagrams(s="abab", p="ab"))
